struct SkiplistNode {
    int _val;
    vector<SkiplistNode*> _next;

    SkiplistNode(int val, int level) : _val(val), _next(level, nullptr) {}
};
class Skiplist {
    using Node = SkiplistNode;

private:
    Node* _head;
    size_t _maxL = 32;
    double _p = 0.25;

public:
    Skiplist() {
        srand(time(0));
        _head = new Node(-1, 1);
    }

    bool search(int target) {
        Node* cur = _head;
        int level = _head->_next.size();
        int leveli = level - 1;
        while (leveli >= 0) {
            if (cur->_next[leveli] && cur->_next[leveli]->_val < target)
                cur = cur->_next[leveli];
            else if (cur->_next[leveli] == nullptr ||
                     cur->_next[leveli]->_val > target)
                leveli--;
            else
                return true;
        }
        return false;
    }

    vector<Node*> findPrevious(int num) {
        Node* cur = _head;
        int level = _head->_next.size();
        vector<Node*> prv(level, _head);

        int leveli = level - 1;
        while (leveli >= 0) {
            if (cur->_next[leveli] && cur->_next[leveli]->_val < num)
                cur = cur->_next[leveli];
            else if (cur->_next[leveli] == nullptr ||
                     cur->_next[leveli]->_val >= num)
                prv[leveli] = cur, leveli--;
        }
        return prv;
    }

    int randomLevel() {
        size_t level = 1;
        while (level < _maxL && rand() <= RAND_MAX * _p)
            ++level;
        return level;
    }
    void add(int num) {
        vector<Node*> prv = findPrevious(num);
        int level = randomLevel();
        Node* node = new Node(num, level);
        if (level > _head->_next.size()) {
            _head->_next.resize(level, nullptr);
            prv.resize(level, _head);
        }

        for (size_t i = 0; i < level; ++i) {
            node->_next[i] = prv[i]->_next[i];
            prv[i]->_next[i] = node;
        }
    }

    bool erase(int num) {
        vector<Node*> prv = findPrevious(num);
        if (prv[0]->_next[0] == nullptr || prv[0]->_next[0]->_val != num)
            return false;
        Node* aim = prv[0]->_next[0];
        for (size_t i = 0; i < aim->_next.size(); ++i) {
            prv[i]->_next[i] = aim->_next[i];
        }
        delete aim;
        int level = _head->_next.size();
        int leveli = level - 1;
        while (leveli >= 0) {
            if (_head->_next[leveli] == nullptr)
                --leveli;
            else
                break;
        }
        _head->_next.resize(leveli + 1);
        return true;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */